import java.util.ArrayList;
import java.util.Dictionary;
import java.util.Hashtable;
import java.util.List;
import java.util.Iterator;

import javax.swing.plaf.basic.BasicInternalFrameTitlePane.MaximizeAction;

public class UTM {

	private class Regla {
		private int i;
		private int j;
		private int k;
		private int l;
		private int m;

		public int getI() {
			return i;
		}

		public void setI(int i) {
			this.i = i;
		}

		public int getJ() {
			return j;
		}

		public void setJ(int j) {
			this.j = j;
		}

		public int getK() {
			return k;
		}

		public void setK(int k) {
			this.k = k;
		}

		public int getL() {
			return l;
		}

		public void setL(int l) {
			this.l = l;
		}

		public int getM() {
			return m;
		}

		public void setM(int m) {
			this.m = m;
		}
		
		public void printRegla(){
			String m="";
			m += Integer.toString(this.getI()) + " ";
			m += Integer.toString(this.getJ()-1) + " ";
			m += Integer.toString(this.getK()) + " ";
			m += Integer.toString(this.getL()-1) + " ";
			if (this.getM() == RIGHT_VALUE){
				m += "R";
			}
			else{
				m += "L";
			}
			System.out.println(m);
		}
	}

	final static int FINAL_STATE = 2;
	final static int RIGHT_VALUE = 2;
	final static int LEFT_VALUE = 1;
	final static int CANT_MT = 10;
	// cinta 1 (M)
	List<Regla> cinta1;

	// cinta 2 (w decodificado)
	List<Integer> cinta2;

	// cinta 3 (estado actual de M)
	List<Integer> cinta3;

	// cinta 4 (scratch)
	ArrayList<String> cinta4;

	public UTM() {

		cinta1 = new ArrayList<Regla>();
		cinta2 = new ArrayList<Integer>();
		cinta3 = new ArrayList<Integer>();
		cinta4 = new ArrayList<String>();

	}

	public boolean setUp(String M, String w) {
		cinta1.clear();
		cinta2.clear();
		cinta3.clear();
		cinta4.clear();
		boolean parseResult = this.parseM(M);
		if (parseResult)
			decodify(w);
		return parseResult;
	}

	// paso 1 mover M a cinta1
	private boolean parseM(String M) {
		boolean result = false;
		String[] rules = M.split("11"); // splitting using a 11 as separator
		for (int i = 0; i < rules.length; i++) {
			Regla regla = new Regla();
			String[] parteDeRegla = rules[i].split("1"); // cada parte de la
															// regla es separada
															// por un 1
			if (parteDeRegla.length == 5) {
				regla.setI(parteDeRegla[0].length()); // el tamano de esa parte
														// de la regla va a ser
														// i, o sea si es 0 = 1
														// o 00 = 2 o 000 = 3 y
														// asi
				regla.setJ(parteDeRegla[1].length());
				regla.setK(parteDeRegla[2].length());
				regla.setL(parteDeRegla[3].length());
				regla.setM(parteDeRegla[4].length());
			} else {// la maquina tiene errores sintacticos
				this.cinta1.clear(); // se limpia la cinta de la maquina
				result = false;
				return result; // se retorna falso
			}
			this.cinta1.add(regla);
			result = true; // el resultado es verdadero porque al menos se
							// agrego una regla a la cinta
		}

		return result;
	}

	// paso 2
	private void decodify(String w) {
		Dictionary<Character, Integer> map = new Hashtable<Character, Integer>();
		map.put('0', 1);
		map.put('1', 2);
		map.put('B', 3);
		char[] input = w.toCharArray();
		for (int i = 0; i < input.length; i++) {
			Integer resultNum = map.get(input[i]);
			if (resultNum != null)
				this.cinta2.add(resultNum);
		}

	}

	// paso 3 ?
	public int start() {

		int i = 1;
		// valor siendo leIdo en la cinta2 (w)
		int posJ = 0;
		int sizeW = this.cinta2.size(); 
		int pasos=0;
		int j,k, l, m,resultadoSearch;
		
		//se comprueba que haya al menos 1 sImbolo en w
		if (sizeW > 0)
		{
			j = this.cinta2.get(posJ);
			resultadoSearch = this.search(i, j);
		}
		else{
			resultadoSearch=-1;
		}

		
		// mientras la bUsqueda de reglas sea exitosa
		while (resultadoSearch >= 0) {
			// existe una regla
			Regla regla = this.cinta1.get(resultadoSearch);
			pasos++;
			k = regla.getK();
			l = regla.getL();
			m = regla.getM();

			// 4.a
			this.cinta3.clear();
			this.cinta3.add(k);
			i = k;
			// 4.b
			this.cinta2.set(posJ, l); // escribir en la cinta2 0^j
			// 4.c
			if (m == RIGHT_VALUE) {
				// adelantamos en la cinta 2
				posJ++;
			} else {
				// retrocedemos
				posJ--;
			}
			// verificar que no nos hemos salido de la cinta
			// y que no se ha terminado
			if (posJ >= 0 && posJ < sizeW) {
				// paso iterativo
				j = this.cinta2.get(posJ);
				resultadoSearch = this.search(i, j);
			} else {
				posJ = -1;
				resultadoSearch=-1;
			}
		}

		/**
		 * hace paso 5 y 6 se acabaron las transciciones o los simbolos en la
		 * cinta2
		 * **/
		this.assertEstadoFinal(i,pasos);
		return pasos;
	}

	// paso 4

	/**
	 * Search
	 * 
	 * @param i
	 *            estado actual
	 * @param j
	 *            lectura de w debe encontrar una regla que comience con i y j
	 *            para aplicar k, l , m
	 * @return devuelve el numero de regla si no la encuentra devuelve -1
	 * **/
	private int search(int i, int j) {
		Iterator<Regla> iReglas = this.cinta1.iterator();
		Regla regla;
		int contador = -1;

		while (iReglas.hasNext()) {
			regla = iReglas.next();
			contador++;

			if (regla.getI() == i && regla.getJ() == j) {
				return contador;
			}
		}
		return -1;
	}

	// paso 5
	private void assertEstadoFinal(int estadoActual, int pasos) {
		String mensaje = "";

		if (FINAL_STATE == estadoActual) {
			mensaje = "************  STRING ACEPTADO  POR M EN ";
		} else {
			mensaje = "************  STRING NO ACEPTADO  POR M EN ";
		}
		
		mensaje+= Integer.toString(pasos);
		mensaje+= " PASOS ************ ";
		System.out.println(mensaje);
	}

	public void imprimirResultados(List<String> mts, List<String> entradas, String[][] resultados){
		int mtC = 0;
		int entradaC = 0;
		System.out.println("*****************  Entradas generadas aleatoriamente ********************* ");
		for(String entrada : entradas)
			System.out.println(String.format("Entrada %d : %s", entradaC++, entrada));
		System.out.println("*****************  Maquinas de Turing generadas aleatoriamente ********************* ");
		for(String mt: mts)
			System.out.println(String.format("MT %d : %s", mtC++, mt));
		
		System.out.println("*****************  Cantidad de pasos para que MT se detenga en la entrada ********************* ");
		for(int i = 0; i < CANT_MT; i++){
			StringBuffer buffer = new StringBuffer();
			buffer.append(String.format("MT %s: ", i));
			for(int j = 0; j < CANT_MT; j++){
				buffer.append(resultados[i][j]);
				buffer.append(" | ");
			}
			System.out.println(buffer.toString());
		}
				
		
	}
	public static void main(String[] args) {

		String M = "01001000101001100010101001001100010010010100110001000100010010";
		// String MaquinaMala =
		// "0100100010100110001010100100110001001001010011000101100100010010";
		String w = "1011";
		String[][] megaTabla = new String[CANT_MT][CANT_MT];
		UTM utm = new UTM();
		TMGenerator tmGen = new TMGenerator();
		List<String> MTs = new ArrayList<String>();
		for(int i=0; i < CANT_MT; i++)
			MTs.add(tmGen.generateMachine(3, 3, 3, 2, 2));
		
		List<String> entradas = new ArrayList<String>();
		for(int i = 0; i < CANT_MT; i++)
			entradas.add(tmGen.generateInputTape());
		
		
		
		for(int i = 0;i < CANT_MT; i++){
			for(int j = 0; j < CANT_MT; j++){
				
				boolean resultadoConfiguration = utm.setUp(MTs.get(i), entradas.get(j));
				if(resultadoConfiguration)
					megaTabla[i][j] = String.valueOf(utm.start());
				else
					megaTabla[i][j] = "N/A";
			}	
		}
		
		utm.imprimirResultados(MTs, entradas, megaTabla);
		
//		System.out.println("Maquina Generada: ");
//		System.out.println(generatedMachine);
//		boolean validate = utm.setUp(generatedMachine,w);
//		// boolean validate=utm.setUp(MaquinaMala, w);
//		if (validate) {
//
//			System.out.println("MAQUINA CONFIGURADA CORRECTAMENTE");
//			System.out.println("Inicia ejecucion");
//			utm.start();
//			System.out.println("Finaliza ejecucion");
//		} else {
//			System.out.println("************  MAQUINA INVALIDA  ***********");
//		}

	}
}
